{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1448c5f7-2fcc-4c1e-af81-2f91ccbd186b",
   "metadata": {},
   "source": [
    "# 322. 零钱兑换\n",
    "\n",
    "给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。\n",
    "\n",
    "计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。\n",
    "\n",
    "你可以认为每种硬币的数量是无限的。\n",
    "\n",
    "\n",
    "示例 1：\n",
    "\n",
    "> 输入：coins = [1, 2, 5], amount = 11  \n",
    "> 输出：3  \n",
    "> 解释：11 = 5 + 5 + 1\n",
    "\n",
    "示例 2：\n",
    "\n",
    "> 输入：coins = [2], amount = 3  \n",
    "> 输出：-1\n",
    "\n",
    "示例 3：\n",
    "\n",
    "> 输入：coins = [1], amount = 0  \n",
    "> 输出：0\n",
    "\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "- 1 <= coins.length <= 12\n",
    "- 1 <= coins[i] <= $2^{31} - 1$\n",
    "- 0 <= amount <= $10^4$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99e503dd-23e6-4d4d-a179-e0c2209add2f",
   "metadata": {},
   "source": [
    "## 1、暴⼒递归"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4042cc7-02b0-4efb-8751-d5917c1974f4",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "```python\n",
    "# 伪码框架\n",
    "def coinChange(coins, amount):\n",
    "    # 定义：要凑出⾦额 n，⾄少要 dp(n) 个硬币\n",
    "    def dp(n):\n",
    "        # 做选择，选择需要硬币最少的那个结果\n",
    "        for coin in coins:\n",
    "            res = min(res, 1 + dp(n - coin))\n",
    "        return res\n",
    "\n",
    "    # 我们要求的问题是 dp(amount)\n",
    "    return dp(amount)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "314249f9-58b7-4eaa-b311-a231445e4779",
   "metadata": {},
   "outputs": [],
   "source": [
    "def coinChange(coins, amount):\n",
    "    def dp(n):\n",
    "        # base case\n",
    "        if n == 0: return 0\n",
    "        if n < 0: return -1\n",
    "\n",
    "        # 求最⼩值，所以初始化为正⽆穷\n",
    "        res = float('inf')\n",
    "        for coin in coins:\n",
    "            subproblem = dp(n - coin)\n",
    "            # ⼦问题⽆解，跳过\n",
    "            if subproblem == -1: continue\n",
    "            res = min(res, 1 + subproblem)\n",
    "\n",
    "        return res if res != float('inf') else -1\n",
    "\n",
    "    return dp(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fb196bd5-68a2-4eb0-abe6-7f0a9dbf5fb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "-1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "print(coinChange([1,2,5],11))\n",
    "print(coinChange([2],3))\n",
    "print(coinChange([1],0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f90d099-19da-409a-ba79-6829380c53a6",
   "metadata": {},
   "source": [
    "## 2、带备忘录的递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d87c4ed7-836e-4313-a2ac-c6ab27fd4c4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def coinChange(coins, amount):\n",
    "    # 备忘录\n",
    "    memo = dict()\n",
    "    def dp(n):\n",
    "        # 查备忘录，避免重复计算\n",
    "        if n in memo: return memo[n]\n",
    "\n",
    "        if n == 0: return 0\n",
    "        if n < 0: return -1\n",
    "        res = float('inf')\n",
    "        for coin in coins:\n",
    "            subproblem = dp(n - coin)\n",
    "            if subproblem == -1: continue\n",
    "            res = min(res, 1 + subproblem)\n",
    "        \n",
    "        # 记⼊备忘录\n",
    "        memo[n] = res if res != float('inf') else -1\n",
    "        return memo[n]\n",
    "        \n",
    "    return dp(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a8e3e267-c764-4f84-bb6e-7573f5402052",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "-1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "print(coinChange([1,2,5],11))\n",
    "print(coinChange([2],3))\n",
    "print(coinChange([1],0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1aa9f21c-4faa-4051-ac12-fda0c4c6d036",
   "metadata": {},
   "source": [
    "## 3、dp 数组的迭代解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "fffebcb7-c40b-4057-bf40-c0b9a1ede8d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def coinChange(coins, amount):\n",
    "    # 数组⼤⼩为 amount + 1，初始值也为 amount + 1\n",
    "    dp = [float('inf')]*(amount+1)\n",
    "\n",
    "    # base case\n",
    "    dp[0] = 0\n",
    "    for i in range(len(dp)):\n",
    "        # 内层 for 在求所有⼦问题 + 1 的最⼩值\n",
    "        for coin in coins:\n",
    "            # ⼦问题⽆解，跳过\n",
    "            if i - coin < 0: continue\n",
    "            dp[i] = min(dp[i], 1 + dp[i-coin])\n",
    "\n",
    "    return -1 if dp[amount] == float('inf') else dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "6f187857-af85-4e25-93b0-7ab9ea9f3924",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "-1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "print(coinChange([1,2,5],11))\n",
    "print(coinChange([2],3))\n",
    "print(coinChange([1],0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a278ef6-de59-40ef-a39e-df95d19c6a17",
   "metadata": {},
   "source": [
    "## 4、回溯打印"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "71a2ad69-0437-44c3-8e5a-ab5be7345aaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def coinChange(coins, amount):\n",
    "    # 数组⼤⼩为 amount + 1，初始值也为 amount + 1\n",
    "    dp = [float('inf')]*(amount+1)\n",
    "    coin_used = [0] * (amount + 1)  # 记录最后使用的硬币\n",
    "\n",
    "    # base case\n",
    "    dp[0] = 0\n",
    "    for i in range(len(dp)):\n",
    "        # 内层 for 在求所有⼦问题 + 1 的最⼩值\n",
    "        for coin in coins:\n",
    "            # ⼦问题⽆解，跳过\n",
    "            if i - coin < 0: continue\n",
    "            if dp[i] > 1 + dp[i-coin]:\n",
    "                dp[i] = 1 + dp[i-coin]\n",
    "                coin_used[i] = coin\n",
    "\n",
    "    if dp[amount] == float('inf'):\n",
    "        print(\"无法组合出目标金额\")\n",
    "        return -1\n",
    "    \n",
    "    # 回溯找出使用的硬币\n",
    "    res = []\n",
    "    remaining = amount\n",
    "    while remaining > 0:\n",
    "        coin = coin_used[remaining]\n",
    "        res.append(coin)\n",
    "        remaining -= coin\n",
    "    \n",
    "    print(f\"最少硬币数: {dp[amount]}, 硬币组合: {res}\")\n",
    "    return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "5fa59115-ebe5-4d96-9aa9-c3d6ab3c8132",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最少硬币数: 3, 硬币组合: [1, 5, 5]\n",
      "3\n",
      "无法组合出目标金额\n",
      "-1\n",
      "最少硬币数: 0, 硬币组合: []\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "print(coinChange([1,2,5],11))\n",
    "print(coinChange([2],3))\n",
    "print(coinChange([1],0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e37961a2-7657-4ec0-9700-cd98966e1c1f",
   "metadata": {},
   "source": [
    "参考资料：\n",
    "- 《labuladong的算法小抄》：背包问题之零钱兑换\n",
    "- 《labuladong的算法秘籍》：⼆、凑零钱问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09eb7195-6d40-48c5-9dbb-c6daebb36352",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
